package com.zjsru.plan2024.oneday;

import java.util.*;

/**
 * 1338. 数组大小减半
 *
 * @Author: cookLee
 * @Date: 2024-12-15
 */
public class MinSetSize {

    /**
     * 主
     * \
     * 输入：arr = [3,3,3,3,5,5,5,2,2,7]
     * 输出：2
     * 解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
     * 大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
     * 选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。
     * \
     * 输入：arr = [7,7,7,7,7,7]
     * 输出：1
     * 解释：我们只能选择集合 {7}，结果数组为空。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        MinSetSize minSetSize = new MinSetSize();
        int[] arr = new int[]{3, 3, 3, 3, 5, 5, 5, 2, 2, 7};
        System.out.println(minSetSize.minSetSize(arr));
    }

    /**
     * 贪心
     *
     * @param arr arr
     * @return int
     */
    public int minSetSize(int[] arr) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int i : arr) {
            countMap.put(i, countMap.getOrDefault(i, 0) + 1);
        }
        //按出现次数进行从大到小排序
        List<Integer> list = new ArrayList<>(countMap.values());
        list.sort(Collections.reverseOrder());
        int ans = 0;
        //记录数组长度
        int countLen = 0;
        for (int i = 0; i < list.size(); i++) {
            //满足要求的数字
            ans += 1;
            //已有整数的长度
            countLen += list.get(i);
            //只要满足要求，就是最小的集合大小
            if (countLen * 2 >= arr.length) {
                break;
            }
        }
        return ans;
    }

}
